/*
 * Copyright (C), 2015-2018
 * FileName: Solution078
 * Author:   zhao
 * Date:     2018/12/19 18:20
 * Description: 78. 子集
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈78. 子集〉
 *
 * @author zhao
 * @date 2018/12/19 18:20
 * @since 1.0.1
 */
public class Solution078 {
    /**************************************
     * 题目
     给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

     说明：解集不能包含重复的子集。

     示例:

     输入: nums = [1,2,3]
     输出:
     [
     [3],
     [1],
     [2],
     [1,2,3],
     [1,3],
     [2,3],
     [1,2],
     []
     ]
     **************************************/

    /*************************************
     想法：
     和077差不多，
         回溯算法： (后面的数据是用下标表示)以1起始数据，然后将2.3.4拼进去；
         再回头以2为起始位置，这时候就不能把1算进去，然后把3.4拼进去
     我的做法
     超过  %的测试案例
     时间复杂度/空间复杂度：  /
     代码执行过程：

     总结：

     ************************************/
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();

        List<Integer> cur = new ArrayList<>();

        dfs(nums, 0, cur, ans);
        return ans;
    }

    private void dfs(int[] nums, int last, List<Integer> cur, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(cur));
        for (int i = last; i < nums.length; i++) {
            cur.add(nums[i]);
            dfs(nums, i + 1, cur, ans);
            cur.remove(cur.size() - 1);
        }
        System.out.println(ans.toString());
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<List<Integer>> better(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            List<Integer> one = new ArrayList<>();
            one.add(num);
            result.add(one);
            int resultSize = result.size();
            for (int j = 0; j < resultSize - 1; j++) {
                List<Integer> newone = new ArrayList<>();
                newone.addAll(result.get(j));
                newone.add(num);
                result.add(newone);
            }
        }
        result.add(new ArrayList<>());
        return result;
    }
}
